~ chicken-core (master) /manual/Module (chicken sort)

 1[[tags: manual]]
 2[[toc:]]
 3
 4== Module (chicken sort)
 5
 6This module contains several procedures which deal with sorting of
 7''sequences'' (i.e., lists and vectors).
 8
 9=== merge
10
11<procedure>(merge LIST1 LIST2 LESS?)</procedure><br>
12<procedure>(merge! LIST1 LIST2 LESS?)</procedure>
13
14Joins two lists in sorted order. {{merge!}} is the destructive
15version of merge. {{LESS?  }} should be a procedure of two arguments,
16that returns true if the first argument is to be ordered before the
17second argument.
18
19
20=== sort
21
22<procedure>(sort SEQUENCE LESS?)</procedure><br>
23<procedure>(sort! SEQUENCE LESS?)</procedure>
24
25Sort {{SEQUENCE}}, which should be a list or a vector. {{sort!}}
26is the destructive version of sort.
27
28
29=== sorted?
30
31<procedure>(sorted? SEQUENCE LESS?)</procedure>
32
33Returns true if the list or vector {{SEQUENCE}} is already sorted.
34
35=== topological-sort
36
37<procedure>(topological-sort DAG PRED)</procedure>
38
39Sorts the directed acyclic graph dag {{DAG}} so that for every edge from vertex
40u to v, u will come before v in the resulting list of vertices.
41
42{{DAG}} is a list of sublists. The car of each sublist is a
43vertex. The cdr is the adjacency list of that vertex, i.e. a list of
44all vertices to which there exists an edge from the car vertex.
45{{pred}} is procedure of two arguments that should compare vertices
46for equality.
47
48Time complexity: O (|V| + |E|)
49
50<enscript highlight=scheme>
51(topological-sort
52       '((shirt tie belt)
53         (tie jacket)
54         (belt jacket)
55         (watch)
56         (pants shoes belt)
57         (undershorts pants shoes)
58         (socks shoes))
59       eq?)
60
61=>
62
63(socks undershorts pants shoes watch shirt belt tie jacket)
64</enscript>
65
66If a cycle is detected during the sorting process, an exception of the
67condition kinds {{(exn runtime cycle)}} is thrown.
68
69---
70Previous: [[Module (chicken repl)]]
71
72Next: [[Module (chicken string)]]